#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义队列结点
typedef struct qnode
{
   char data;
   struct qnode *next;
} QNode;

// 定义队列, 未指定队列大小
typedef struct lNode
{
   QNode *front;
   QNode *rear;
} LNode, *LinkQueue;

// 初始化链队列. 带头结点的链队列
void initQueue(LinkQueue LQ)
{
   LQ->front = (QNode *)malloc(sizeof(QNode));
   LQ->rear = LQ->front; // 尾指针等于头指针，修改尾指针相当于修改头指针
   // 带头结点
   LQ->rear->next = NULL;
}

int queueEmpty(LinkQueue LQ)
{
   return LQ->front == LQ->rear;
}

void enQueue(LinkQueue LQ, char x)
{
   QNode *p = (QNode *)malloc(sizeof(QNode));
   p->data = x;
   p->next = NULL;
   LQ->rear->next = p;
   // 队尾指针指向新的队尾结点
   LQ->rear = p;
}

char deQueue(LinkQueue LQ)
{
   if (queueEmpty(LQ))
   {
      printf("queue is empty\n");
      exit(0);
   }

   QNode *p = LQ->front;
   // 头指针指向原对头结点
   LQ->front = LQ->front->next;
   free(p);
   return LQ->front->data;
}

char getFront(LinkQueue LQ)
{
   if (queueEmpty(LQ))
   {
      printf("getFront queue is empty\n");
      return CHAR_MIN;
   }
   return LQ->front->next->data;
}

// 例题: 循环链队列
QNode *init()
{
   // 头结点
   QNode *q = (QNode *)malloc(sizeof(QNode));
   q->next = NULL;
   return q;
}

void EQueue(QNode *q, char x)
{
   QNode *s = (QNode *)malloc(sizeof(QNode));
   s->data = x;
   s->next = q->next;
   q->next = s;
   printf("EQueue=====s=%p\n", s);
   // q = s;
   printf("EQueue=====%p\n", q);
}

char DQueue(QNode *q)
{
   printf("DQueue=====%p\n", q);
   if (q->next == NULL)
   {
      printf("queue is empty\n");
      exit(0);
   }

   QNode *s = q->next;
   q->next = s->next;
   printf("s=====%p, snext=%p\n", s, s->next);
   char x = s->data;
   free(s);
   printf("queue pop=%c\n", x);
   return x;
}

int main()
{
   // BUG: 出栈顺序有问题
   QNode *qq = init();
   printf("ok=====%p\n", qq);
   EQueue(qq, 'a');
   EQueue(qq, 'b');

   DQueue(qq);
   DQueue(qq);

   exit(0);

   LNode n;
   LinkQueue Q = &n; // 防止Q未定义，导致奇怪问题

   initQueue(Q);

   enQueue(Q, 'a');
   enQueue(Q, 'b');
   printf("the front element>>%c\n", getFront(Q));

   deQueue(Q);
   printf("the front element>>%c\n", getFront(Q));
   deQueue(Q);
   deQueue(Q);
   return 0;
}